﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace www.interviewstreet.com.StringReduction
{
    class Program
    {
        
        
        static void Main(string[] args)
        {

            int n = Convert.ToInt32(Console.ReadLine());
            List<int> ans = new List<int>();

            for (int i = 0; i < n; i++)
            {
                string input = Console.ReadLine().ToLower();
                ans.Add(reduceString(input));
                
            }


            
            ans.ForEach(p=>Console.WriteLine(p));
            
           

            
            Console.ReadLine();
        }

        private static int reduceString(string input)
        {
            Queue<string> x = new Queue<string>();
            int minLength = input.Length;
            x.Enqueue(input);
            string s = "";
            while (x.Count>0)
            {
                s = x.Dequeue();
                if (minLength > s.Length)
                    minLength = s.Length;
                for (int i = 0; i < s.Length-1; i++)
                {
                    
                    string substring = s.Substring(i,  2);
                    if(substring.Length<2)
                        continue;
                    string tempStr = "";

                    if (substring == "ab" || substring == "ba")
                    {
                        tempStr = s.Substring(0, i) + 'c' + s.Substring(i + 2);
                    }
                    else if ((substring == "bc" || substring == "cb"))
                    {
                        tempStr=(s.Substring(0, i) + 'a' + s.Substring(i + 2));
                    }
                    else if ((substring == "ac" || substring == "ca"))
                    {
                        tempStr=(s.Substring(0, i) + 'b' + s.Substring(i + 2));
                    }
                    if (tempStr!=substring && tempStr!="")
                    {
                        x.Enqueue(tempStr);
                    }

                }
            }

            return minLength;
        }

        public static bool IsAllEqual(string s)
        {
            return s.Reverse() == s;

        }
    }

    
}
